package org.example.myleet.p526;

/**
 * 全排列爆搜DFS，复杂度O(!n)
 */
public class Solution {
    private int count = 0;

    public int countArrangement(int n) {
        count = 0;
        boolean[] visited = new boolean[n + 1];
        arrange(visited, 1, n);
        return count;
    }

    private void arrange(boolean[] visited, int curIdx, int n) {
        if (curIdx > n) {
            ++count;
            return;
        }
        for (int i = 1; i <= n; ++i) {
            if (visited[i]) {
                continue;
            }
            if (i % curIdx == 0 || curIdx % i == 0) {
                visited[i] = true;
                arrange(visited, curIdx + 1, n);
                visited[i] = false;
            }
        }
    }
}
